package fun.ipconfig.avl;

import fun.ipconfig.DataCompare;

/**
 * 实现平衡二叉树
 *
 * @author gtinlian
 * @mail gtinlian@sina.com
 */
public class AvlTreeNode<T extends DataCompare> {
    private T data;
    private AvlTreeNode<T> l;
    private AvlTreeNode<T> r;
    private AvlTreeNode<T> p;
    private int h;

    /**
     * @return the data
     */
    public T getData() {
        return data;
    }
    public int getH() {
        return h;
    }

    public AvlTreeNode(T data) {
        this.data = data;
        l = null;
        r = null;
        p = this;
        h = 1;
    }

    /**
     * 重置高度
     *
     * @param n
     */
    private void resetHigth(AvlTreeNode<T> n) {
        int lh = getH(n.l);
        int rh = getH(n.r);
        n.h = lh > rh ? lh + 1 : rh + 1;
    }

    /**
     * 判断是否失衡
     *
     * @return 平衡返回true 失衡返回false
     */
    private boolean isAvl() {
        int lh = getH(l);
        int rh = getH(r);
        int Avl = lh - rh;
        return !(Avl > 0 ? Avl >= 2 : Avl <= -2);

    }

    /**
     * 获取节点的高度，如果节点为null则高度为0
     *
     * @param n
     * @return
     */
    private int getH(AvlTreeNode<T> n) {
        return n != null ? n.h : 0;
    }

    /**
     * 节点状态
     *
     * @return
     */
    private AvlStatus getAvlstatus() {
        if (isAvl()) {
            return AvlStatus.NONE;
        } else if (getH(l) > getH(r)) {
            if (getH(l.l) < getH(l.r)) {
                return AvlStatus.LR;
            }
            return AvlStatus.LL;
        } else {
            if (getH(r.r) < getH(r.l)) {
                return AvlStatus.RL;
            }
            return AvlStatus.RR;
        }
    }

    /**
     * 获取插入点
     *
     * @param node
     * @return
     */
    public AvlTreeNode<T> find(T node) {
        AvlTreeNode<T> result = nextNode(node, true);
        return result.data.index() == node.index() ? result : null;
    }

    AvlTreeNode<T> nextNode(T node) {
        return nextNode(node, false);
    }

    AvlTreeNode<T> nextNode(T node, boolean find) {
        AvlTreeNode<T> next = this;
        while (true) {
            if (next.data.index() > node.index()) {
                if (next.l == null) {
                    return next;
                }
                next = next.l;
            } else if (next.data.index() < node.index()) {
                if (next.r == null) {
                    return next;
                }
                next = next.r;
            } else {
                if (find) {
                    return next;
                }
                return null;
            }
        }

    }

    /**
     * LL状态失衡处理
     *     node3           node2
     *     /               /     \
     *   node2           node1   node3
     *   /
     * node1
     *
     * @return
     */
    private AvlTreeNode<T> LL() {
        AvlTreeNode<T> parent = p == this ? this.l : p;
        AvlTreeNode<T> node = l;
        // 将node2 移动到最顶部
        node.p = parent;
        if (parent.l == this) {
            parent.l = node;
        } else if (parent.r == this) {
            parent.r = node;
        }
        // 将node2 rigth 移动到node3 的left
        if (node.r != null) {
            l = node.r;
            node.r.p = this;
        } else {
            l = null;
        }
        // 将node3 移动过到 node2 rigth
        node.r = this;
        p = node;
        if (node.l != null) {
            resetHigth(node.l);
        }
        resetHigth(this);
        return l;
    }

 /**
     * 如果使用LL方法处理失衡结果
     *   node3             node1
     *  /                       \
     *node1                     node3
     *   \                      /
     *  node2                 node2
     * <p>
     * -----------------|--------------------|--------------------|         
     * 先l => rr 再 ll  |         调用l.rr    |           调用ll   |     
     * -----------------|--------------------|--------------------|         
     *   node3          |         node3      | =>      node2      |  
     *   /              |         /          | =>     /     \     |   
     * node1            | =>     node2       | =>   node1   node3 |       
     *     \            | =>    /            |                    |        
     *     node2        | =>   node1         |                    |          
     *------------------|--------------------|--------------------|        
     * @return
     */
    private AvlTreeNode<T> LR() {
        // 先右旋
        l.RR();
        resetHigth(l);
        // 再左旋
        LL();
        return p;
    }

    /**
     * RR 状态的失衡处理
     * node1                 node2
     *      \               /     \
     *     node2          node1   node3
     *         \
     *         node3
     *
     * @return
     */
    private AvlTreeNode<T> RR() {
        AvlTreeNode<T> parent = p == this ? r : p;
        AvlTreeNode<T> node = r;
        // 将node2 移动到最顶部
        node.p = parent;
        if (parent.l == this) {
            parent.l = node;
        } else if (parent.r == this) {
            parent.r = node;
        }
        // node2 的left 移动过到 node1 的right
        if (node.l != null) {
            node.l.p = this;
            r = node.l;
        } else {
            r = null;
        }
        // 将node1 移动到 node2 的left
        p = node;
        node.l = this;
        if (node.r != null) {
            resetHigth(node.r);
        }
        resetHigth(this);
        return node;
    }

    /**
     * 如果使用RR 方法处理失衡结果
     * node1                   node3
     *     \                  /
     *     node3            node1
     *    /                    \
     * node2                  node2
     * ------------------------|--------------------|------------|
     * 先r=> ll再rr            | 调用r.ll            | 调用rr     |
     * ------------------------|--------------------|------------|
     * node1      |      node1         |=>        node2          |
     *     \      |          \         |=>       /     \         |
     *     node3  |  =>      node2     |=>    node1   node3      |
     *     /      |  =>          \     |                         |
     *  node2     |  =>          node3 |                         |
     * -----------|--------------------|-------------------------|
     *
     * @return
     */
    private AvlTreeNode<T> RL() {
        // 先左旋
        r.LL();
        resetHigth(r);
        // 再右旋
        RR();
        return p;
    }

    /** 插入操作 */
    public AvlTreeNode<T> insert(T data) {
        AvlTreeNode<T> indexNode = nextNode(data);
        if (indexNode == null) {
            return this;
        }
        AvlTreeNode<T> node = new AvlTreeNode<T>(data);
        if (indexNode.data.index() > data.index()) {
            indexNode.l = node;

        } else if (indexNode.data.index() < data.index()) {
            indexNode.r = node;
        }
        node.p = indexNode;
        return REAvl(indexNode);
    }

    /**
     * 删除数据，如果全部删除将返回null
     * @param data
     * @return
     */
    public AvlTreeNode<T> delete(T data) {
        AvlTreeNode<T> node = find(data);
        AvlTreeNode<T> leftChangeNode = null;
        if(node == null){
            return this;
        }else if(node.l == null && node.r == null){
            if(node.p == node){
                return null;
            }
            leftChangeNode = node.p;
            if(node.p.l == node){
                node.p.l = null;
            }else{
                node.p.r = null;
            }
            node.p = null;
        }else if(node.l == null){
            if(node == this){
                // 进行数据替换，省略掉节点替换的繁琐
                node.data = node.r.data;
                node.h = 1;
                node.r.p = null;
                node.r = null;
                return node;
            }else{
                if(node.p.l == node){
                    node.p.l = node.r;
                }else{
                    node.p.r = node.r;
                }
                node.r.p = node.p;
                leftChangeNode = node.p;
                node.r = null;
                node.p = null;
            }
        }else if(node.r == null){
            if(node == this){
                // 进行数据替换，省略掉节点替换的繁琐
                node.data = node.l.data;
                node.h = 1;
                node.l.p = null;
                node.l = null;
                return node;
            }else{
                if(node.p.l == node){
                    node.p.l = node.l;
                }else{
                    node.p.r = node.l;
                }
                node.l.p = node.p;
                leftChangeNode = node.p;
                node.l = null;
                node.p = null;
            }
        }else{
            AvlTreeNode<T> next = node.l.r;
            if(node.l.r == null){
                node.data = node.l.data;
                leftChangeNode = node;
                node.l.p = null;
                node.l = null;
            }else{
                while(next.r != null){
                    next = next.r;
                }
                next.p.r = next.l;
                if(next.l != null){
                    next.l.p =  next.p;
                }
                leftChangeNode = next.p;
                // 进行数据替换，省略掉节点替换的繁琐
                node.data = next.data;
                next.l = null;
                next.p = null;
            }
        }
        resetHigth(leftChangeNode);
        return REAvl(leftChangeNode);
    }

    /**
     * 平衡处理
     */
    public AvlTreeNode<T> REAvl(AvlTreeNode<T> indexNode) {

        boolean breakItem = false;
        // 往回处理
        while (true) {
            resetHigth(indexNode);
            if (!indexNode.isAvl()) {
                AvlStatus status = indexNode.getAvlstatus();
                // 处理失衡
                switch (status) {
                    case LL:
                        indexNode.LL();
                        breakItem = false;
                        break;
                    case LR:
                        indexNode.LR();
                        breakItem = false;
                        break;
                    case RR:
                        indexNode.RR();
                        breakItem = false;
                        break;
                    case RL:
                        indexNode.RL();
                        breakItem = false;
                        break;
                    default:
                        break;
                }
            } else {
                indexNode = indexNode.p;
            }
            if (breakItem) {
                return indexNode;
            }
            // 结束条件
            if (indexNode.p == indexNode) {
                breakItem = true;
            }
        }
    }

    /**
     * 提供较好的树可视化打印
     */
    @Override
    public String toString() {
        StringBuffer bf = new StringBuffer("");
        AvlTreeNode tn = this;
        while (true) {
            if (tn.p == tn) {
                break;
            }
            tn = tn.p;
            bf.append("\t");
        }
        return "{" +
                "data:" + data.index() +
                (l != null ? "\n\t" + bf.toString() : " ") + "l:" + l +
                (r != null ? "\n\t" + bf.toString() : " ") + "r:" + r +
                (l != null || r != null ? bf : " ") + "h:" + h +
                "}\n";
    }
}
